﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol17
{
    Dictionary<char,string> map = new Dictionary<char,string>();
    IList<string> res = new List<string>();
    public IList<string> LetterCombinations(string digits)
    {
        int len=digits.Length;
        Console.WriteLine(len);
        if (len == 0 )
        {

        return res; 

        }
        map.Add('2', "abc");
        map.Add('3', "def");
        map.Add('4', "ghi");
        map.Add('5', "jkl");
        map.Add('6', "mno");
        map.Add('7', "pqrs");
        map.Add('8', "tuv");
        map.Add('9', "wxyz");

        
   
        string newStr = null;
       
        DFS(0,digits.Length, digits,newStr);
        return res;

    }

    void DFS(int curIndex, int len, string digits, string newStr)
    {

        Console.WriteLine("curIndex:    "+curIndex+ "    len:  "+len);
        //递归终止的条件
        if (curIndex == len)
        {
            res.Add(newStr);
            return;
        }
        

            //取出这一层需要加入的数字对应的字母串
            
            string curStr = map[digits[curIndex]];

        
       
        for(int i = 0; i < curStr.Length; i++)
        {
            newStr += curStr[i];
            DFS(curIndex + 1, len, digits, newStr);
            //回溯
             newStr = newStr.Substring(0, newStr.Length - 1);


        }
       

    }
}

class Program17
{

    static void Main17(string[] args)
    {
        string digits = "23";
        Sol17 sol = new Sol17();
        IList<string> res= sol.LetterCombinations(digits);
        for (int i = 0; i < res.Count; i++) {


            Console.WriteLine("res:  "+res[i]);
        }


    }
}
